1. Field of the Invention
The present invention relates to a route selection method for selecting a route satisfying a condition with regard to a plurality of Quality of Service (QoS) out of routes each connecting a start point to an end point, and in particular to a route selection method, responsive to an approximation proportion of cost specified beforehand, for selecting a route satisfying a condition with regard to a plurality of QoSs a low cost within the approximation proportion.
2. Description of the Related Art
For high utilization of a network, a route selection technique simultaneously satisfying a desired condition with regard to a plurality of QoSs, such as the bandwidth, transmission delay, and error rate, of a communication route at a low cost is necessary and indispensable. Also in ATM (Asynchronous Transfer Mode) spreading in recent years, a QoS such as cell delay variation tolerance, cell transfer delay, and cell loss ratio are defined. The importance of the communication route selection technique capable of satisfying a desired condition with regard to a plurality of QoSs is increasing. According to their properties, a QoS can be classified broadly into the following three kinds.
(1) Additive property
It is such a property that the QoS value of a route becomes the sum of QoS values of respective links forming the route. For example, the transmission delay and the cell transfer delay come under the property.
(2) Multiplicative property
It is such a property that the QoS value of a route becomes a function of product of QoS values of respective links forming the route. For example, the error rate and the cell loss ratio come under the property.
(3) Concave property
It is such a property that the QoS value of a route becomes the minimum value among QoS values of respective links forming the route. For example, the bandwidth comes under the property.
As a conventional technique for selecting a low cost route satisfying a condition with regard to a plurality of QoSs, "rule-based route selecting system" will now be described by referring to a flow chart of FIG. 8. It is now assumed on a network having ten nodes (A to J) as shown in FIG. 9 that a route satisfying all desired QoS conditions from a node A (start point) to a node J (end point) and requiring the lowest cost is selected. In addition, it is now assumed that the link cost, bandwidth, transmission delay, and error rate between nodes have values as shown in FIG. 10, and QoS conditions to be satisfied are the following three conditions.
QoS condition 1--The bandwidth should be at least 3. PA1 QoS condition 2--The transmission delay should be at most 16. PA1 QoS condition 3--The error rate should be at most 0.05.
At step S71, links which do not satisfy the desired conditions with regard to the bandwidth which is the concave QoS are excepted. In the present implementation form, the bandwidth between D and J is "2" and hence it does not satisfy the QoS condition 1. Therefore, the route DJ is excepted from the subjects of the route selection. At step S72, the other QoS conditions to be satisfied are provided with priorities, and a maximum number of times of trial N described later in detail is determined. The present implementation form will be described, assuming that the QoS condition 2 (transmission delay) is provided with a priority higher than that of the QoS condition 3 (error rate) and the maximum number of times of trial N is set to 2.
At step S73, the cost function or one of the QoS conditions is selected. At first, however, the cost function is always selected. At step S74, the condition selected at the step S73, i.e., at first a route P0 minimizing the cost function is selected regardless of other QoS conditions. In the example shown in FIG. 10, the route P0 of the start point A.fwdarw.G.fwdarw.H.fwdarw.I.fwdarw.the end point J is selected. At step S75, it is determined whether the route P0 satisfies all of the QoS conditions. In the route P0, the transmission delay becomes "28" and hence the QoS condition 2 is not satisfied. Therefore, the processing proceeds to step S78.
At the step S78, it is determined whether the number of times of trial n (=1) has exceeded the maximum number of times of trial N (=2). Since n is not yet exceeded in this case, the processing proceeds to step S77, where the number of times of trial n is increased by one, and the processing returns to the step S73. At the step S73, the QoS condition 2 (transmission delay) having a higher priority is selected this time. At the step S74, a route P1 minimizing the transmission delay is selected regardless of other QoS conditions.
In the present implementation form, the route P1 of the start point A.fwdarw.E.fwdarw.H.fwdarw.I.fwdarw.end point J is selected. At the step S75, it is determined whether the route P1 satisfies all other QoS conditions simultaneously. In the present implementation form, the error rate in the route P1 becomes at most 0.05 and consequently the QoS condition 3 is satisfied. Since all other QoS conditions are thus satisfied, the processing proceeds to step S76. At the step S76, the route P1 is output as an optimum route. If the decision at the step S75 becomes negation repeatedly and the number of times of trial n has exceeded the maximum number of times of trial N at the step S78, then information representing that there is no route satisfying the conditions is output at step S79.
The above described conventional technique had the following problems.
(1) The approximation precision depends upon the empirical law.
At the step S72, each QoS condition is provided with a priority on the basis of the empirical law of the user. According to the priority, it is successively determined whether there is a route satisfying each QoS condition. Without the knowledge concerning the kind and property of each QoS condition, an optimum route or a route having a high approximation precision cannot be selected.
For example, contrary to the foregoing description, it is now assumed that the QoS condition 3 (error rate) is provided at the step S72 with a priority higher than that of the QoS condition 2 (transmission delay) . At the step S73, in this case, a route represented as the start point A.fwdarw.B.fwdarw.C.fwdarw.F.fwdarw.the end point J is represented as the minimum error rate route P2. This route P2 has a transmission delay of "14", and satisfy all QoS conditions. And the sum of the link costs of the route P2 is "26", and it becomes less than the cost "32" of the route P1.
Since the selected route thus differs depending upon how QoSs are provided with priorities, the approximation precision depends upon the empirical law. If the number r of the QoS conditions increases, the number of ways of providing QoSs with priorities increases as represented by r!=r.times.(r-1).times. . . . 2.times.1. Therefore, the approximation precision furthermore depends upon the empirical law.
(2) The approximation precision is fixed.
The approximation proportion is fixedly determined by the network configuration such as the number or cost of nodes and links, bandwidth, transmission delay, and error rate. There occurs such a situation that network resources satisfying QoS conditions desired by the network provider or the network users cannot be flexibly assigned.
For example, in the above described conventional system, a route A.fwdarw.E.fwdarw.H.fwdarw.I.fwdarw.J minimizing the transmission delay irrespective of the cost is selected. However, the sum of link costs of this route is "32", whereas the sum of link costs of the optimum solution is "14". The approximation ratio is 32/14, i.e., approximately 2.3. Therefore, the maximum value of the approximation ratio, i.e., the approximation proportion of the conventional technique in an arbitrary network becomes at least 2.3.
In the above described conventional technique, the approximation proportion is fixedly determined by the network configuration such as the link cost. Even if it is attempted to derive a route having a higher approximation precision in an arbitrary network by, for example, making the approximation proportion less than 2.3, therefore, such a demand is not satisfied, resulting in a problem.